package com.Oct_TwentyEight;

import java.util.*;

/**
 * 907. 子数组的最小值之和
 * 给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
 *
 * 由于答案可能很大，因此 返回答案模 10^9 + 7 。
 *
 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/sum-of-subarray-minimums
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 *2022/10/28 11:04
 */

public class Solution907 {

    private final int mod=1000000007;

    public int sumSubarrayMins(int[] arr) {
        int[] left=new int[arr.length];
        int[] right=new int[arr.length];
        int n=arr.length;
        Stack<Integer> deque=new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!deque.isEmpty()&&arr[deque.peek()]>arr[i])
            {
                deque.pop();
            }
            if (deque.isEmpty())
            {
                left[i]=-1;
            }else
            {
                left[i]=deque.peek();
            }
            deque.push(i);
        }
        deque.clear();
        for (int i =n-1; i >=0; i--) {
            while (!deque.isEmpty()&&arr[deque.peek()]>=arr[i])
            {
                deque.pop();
            }
            if (deque.isEmpty())
            {
                right[i]=n;
            }else
            {
                right[i]=deque.peek();
            }
            deque.push(i);
        }
        long ans=0;
        for (int i=0;i<n;i++)
        {
            ans=(ans+ (long) (i - left[i]) *(right[i]-i)*arr[i])%mod;
        }
        return (int) ans;
    }

    public static void main(String[] args) {
        Solution907 solution907=new Solution907();
        System.out.println(solution907.sumSubarrayMins(new int[]{3,1,2,4}));
    }
}
